from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = []

        # n-2留给后面两个数
        for i in range(len(nums)-2):
            s = nums[i]
            # 要求i> 0 因为0的上一个数,不存在
            if i > 0 and nums[i] == nums[i-1]:
                continue

            if nums[i] + nums[i+1] + nums[i+2] > 0:
                break

            if nums[i] + nums[-1] + nums[-2] < 0:
                continue

            j= i+ 1
            k = n -1

            while j < k:
                x  = s + nums[j] + nums[k]
                if x > 0:
                    k -= 1
                elif x < 0:
                    j +=1
                else:
                    ans.append([s,nums[j],nums[k]])
                    j += 1
                    while j < k and nums[j-1] == nums[j]:
                        j += 1
                    k -= 1
                    while j < k and nums[k+1] == nums[k]:
                        k -= 1
        return ans


        


a = Solution()
print(a.threeSum([-1, 0, 1, 2, -1, -4, -2, 3, 0]))